package sort;

public class MergeSort {
    /**
     * merge two ordered list A[p..q] and A[q+1..r] to ordered A[p..r]
     * @param A list to be sorted
     * @param p first element location of A
     * @param q partition element location of A
     * @param r last element location of A
     * @note use two list and sentry, then merge the two sorted list to A[p..r]
     */
    public static void merge(int[] A, int p, int q, int r) {
        int n1 = q - p + 1;
        int n2 = r - q;
        int[] L = new int[n1 + 1];
        int[] R = new int[n2 + 1];

        // copy A[p..q] to L[0..n1-1]
        for (int i = 0; i < L.length - 1; i++) {
            L[i] = A[p+i];
        }
        // copy A[q+1..r] to R[0..n2-1]
        for (int j = 0; j < R.length - 1; j++) {
            R[j] = A[q+1+j];
        }

        // set sentry using ∞ (max value)
        L[n1] = Integer.MAX_VALUE;
        R[n2] = Integer.MAX_VALUE;

        int i = 0;
        int j = 0;
        for (int k = p; k <= r; k++) { // case k==r is necessary, because r is the element with max index in A , not the length
            if (L[i] <= R[j]) { // "=" can't be absent, otherwise the sort is not stable
                A[k] = L[i];
                i++;
            }else {
                A[k] = R[j];
                j++;
            }
        }
    }

    /**
     * merge two ordered list A[p..q] and A[q+1..r] to ordered A[p..r]
     * @param A list to be sorted
     * @param p first element location of A
     * @param q partition element location of A
     * @param r last element location of A
     * @note merge two segment to new list, then re-copy back to origin list
     */
    public static void merge_2(int[] A, int p, int q, int r) {
        int[] L = new int[r - p + 1];

        /* merge A[p..q] and A[q+1..r] to L[0..length-1] by asc order */
        int i = p;
        int j = q+1;
        int k = 0;
        while (i <= q && j <= r) {
            if(A[i] <= A[j]) { // "=" can't be absent, otherwise the sort is not stable
                L[k] = A[i];
                i++;
            }
            else {
                L[k] = A[j];
                j++;
            }

            k++;
        }

        // copy left element to L
        while (i <= q) {
            L[k++] = A[i++];
        }
        while (j <= r) {
            L[k++] = A[j++];
        }

        // copy new sorted list L to origin list A
        for (int t = 0; t < L.length; t++) {
            A[p+t] = L[t];
        }
    }

    public static void mergeSort(int[] A, int p, int r) {
        if (p < r) {
            int q = (p + r) / 2;
            mergeSort(A, p, q);
            mergeSort(A, q+1, r);
            merge(A, p, q, r);
        }
    }
}
